package com.zds.leetcode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class q_102 {
    public static void main(String[] args) {
        // 创建树的示例
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        root.right.right = new TreeNode(6);

        // 执行层序遍历
        System.out.println(levelOrderTraversal(root));
    }

    public static List<List<Integer>> levelOrderTraversal(TreeNode root) {
        List<List<Integer>> result =  new LinkedList<>();
        if (root == null) {
            return result;
        }

        Queue<TreeNode> queue = new LinkedList<>();

        queue.add(root);

        while (!queue.isEmpty()) {
            List<Integer> list = new ArrayList<>();

            // 当前层节点个数，记得需要提前取出来，因为后续要对queue进行操作
            int count = queue.size();

            // 弹出当前层所有节点
            for (int i = 0;i < count;i++){
                TreeNode current = queue.poll();

                // 处理当前节点，例如打印节点值
                list.add(current.val);

                // 如果左节点存在，将其加入队列
                if (current.left != null) {
                    queue.add(current.left);
                }

                if (current.right != null) {
                    queue.add(current.right);
                }
            }
            result.add(list);
        }
        return result;
    }
}
